package com.yww.leetcode2.array;

/**
 * @author yww
 * @description 二分查找704
 * @since 2024/9/25
 */
public class BinarySearch704_01 {
    public int search(int[] nums, int target) {
        return search2(nums, target);
    }

    // [left, right]
    public static int search1(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        // left,right都是合法区间
        while (left <= right) {
            int middle = (left + right) >> 1;
            if (nums[middle] > target) { // 中间值大于target，缩小范围
                right = middle - 1;
            } else if (nums[middle] < target) { // 中间值小于target，扩大范围
                left = middle + 1;
            } else {
                return middle;
            }
        }
        return -1;
    }

    // [left, right)
    public static int search2(int[] nums, int target) {
        int left = 0;
        int right = nums.length;

        // left,right都是合法区间
        while (left < right) {
            int middle = (left + right) >> 1;
            if (nums[middle] > target) { // 中间值大于target，缩小范围
                right = middle;
            } else if (nums[middle] < target) { // 中间值小于target，扩大范围
                left = middle + 1;
            } else {
                return middle;
            }
        }
        return -1;
    }
}
